package com.归并排序;

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;

public class Solution {

	public static int[] MergeSort(int a[]) {
		if(a.length<2)return a;
		
		int mid = a.length/2;
		int left[] = Arrays.copyOfRange(a, 0, mid);//包含左边下表，不包含右边下标记
		int right[] = Arrays.copyOfRange(a, mid, a.length);
		return Merge(MergeSort(left),MergeSort(right));
	}
     private static int[] Merge(int left[],int right[]) {
    	 AtomicInteger a = new AtomicInteger(1);
    	 
    	 int l=0,r=0;
    	 int res[] = new int[left.length+right.length];
    	 for(int index=0;index<res.length;index++) {
    		 if(r>=right.length) {
    			 res[index] = left[l++];
    		 }
    		 else if(l>=left.length) {
    			 res[index] = right[r++];
    		 }
    		 else if(left[l]<right[r]) {
    			 res[index] = left[l++];
    		 }
    		 else {
    			 res[index] = right[r++];
    		 }
    	 }
		return res;
		
    	 
     }
}
